﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// do googlil som sa, poziciaviam si kod, (neoveroval som spravnost, treba checknut)
// http://mihkeltt.blogspot.sk/2009/04/dameraulevenshtein-distance.html
// http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance


namespace wUniAppPCL
{
  public static class DamerauLevenshtein
  {
    public static int DamerauLevenshteinDistanceTo(this string @string, string targetString)
    {
      return DamerauLevenshteinDistance(@string, targetString);
    }
    public static int DamerauLevenshteinDistance(string string1, string string2)
    {
      if (String.IsNullOrEmpty(string1))
      {
        if (!String.IsNullOrEmpty(string2))
          return string2.Length;
        return 0;
      }

      if (String.IsNullOrEmpty(string2))
      {
        if (!String.IsNullOrEmpty(string1))
          return string1.Length;
        return 0;
      }

      int length1 = string1.Length;
      int length2 = string2.Length;
      int[,] d = new int[length1 + 1, length2 + 1];
      int cost, del, ins, sub;

      for (int i = 0; i <= d.GetUpperBound(0); i++)
        d[i, 0] = i;

      for (int i = 0; i <= d.GetUpperBound(1); i++)
        d[0, i] = i;

      for (int i = 1; i <= d.GetUpperBound(0); i++)
      {
        for (int j = 1; j <= d.GetUpperBound(1); j++)
        {
          if (string1[i - 1] == string2[j - 1])
            cost = 0;
          else
            cost = 1;

          del = d[i - 1, j] + 1;
          ins = d[i, j - 1] + 1;
          sub = d[i - 1, j - 1] + cost;
          d[i, j] = Math.Min(del, Math.Min(ins, sub));

          if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
            d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
        }
      }
      return d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
  }
}

